import java.util.*;

public class leetcode733_像素渲染 {
    public static void main(String[] args) {
        Solution6 solution6 = new Solution6();
        int[][] image = new int[][] {{0, 0, 0}, {0,0,0}};
        solution6.floodFill(image, 1, 0, 2);
    }
}

// 广度搜索优先
class Solution5 {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        if (image[sr][sc] == color) {
            return image;
        }

        Queue<int[]> queue = new LinkedList<>();

        // n为二维数组行数，m为二维数组列数，src为原始值
        int n = image.length, m = image[0].length, src = image[sr][sc];

        // 维护一个和image相同大小的二维数组，避免向队列中重复添加数据，原始数据均为0，当image中某个元素被使用后，flag数组相应位置元素置为1
        int[][] flag = new int[image.length][];
        for (int i = 0; i < image.length; i++) {
            flag[i] = new int[image[0].length];
        }

        queue.offer(new int[] {sr, sc});
        while (!queue.isEmpty()) {
            int[] xy = queue.poll();
            int x = xy[0], y = xy[1];
            flag[x][y] = 1;
            image[x][y] = color;

            // 遍历上下左右节点
            int[][] dirs = new int[][] {{x-1, y}, {x+1, y}, {x, y-1}, {x, y+1}};
            for (int[] dir : dirs) {
                if (dir[0] >= 0 && dir[1] >= 0 && dir[0] < n && dir[1] < m && image[dir[0]][dir[1]] == src
                        && flag[dir[0]][dir[1]] == 0) {
                    flag[dir[0]][dir[1]] = 1;
                    queue.offer(dir);
                }
            }
        }
//        Arrays.stream(image).forEach(p -> System.out.println(Arrays.toString(p)));
        return image;
    }
}


// 深度搜索优先
class Solution6 {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        if (image[sr][sc] == color) {
            return image;
        }

        Stack<int[]> stack = new Stack<>();

        // n为二维数组行数，m为二维数组列数，src为原始值
        int n = image.length, m = image[0].length, src = image[sr][sc];

        // 维护一个和image相同大小的二维数组，避免向队列中重复添加数据，原始数据均为0，当image中某个元素被使用后，flag数组相应位置元素置为1
        int[][] flag = new int[image.length][];
        for (int i = 0; i < image.length; i++) {
            flag[i] = new int[image[0].length];
        }

        stack.push(new int[] {sr, sc});
        while (!stack.isEmpty()) {
            int[] xy = stack.pop();
            int x = xy[0], y = xy[1];
            flag[x][y] = 1;
            image[x][y] = color;

            // 遍历上下左右节点
            int[][] dirs = new int[][] {{x-1, y}, {x+1, y}, {x, y-1}, {x, y+1}};
            for (int[] dir : dirs) {
                if (dir[0] >= 0 && dir[1] >= 0 && dir[0] < n && dir[1] < m && image[dir[0]][dir[1]] == src
                        && flag[dir[0]][dir[1]] == 0) {
                    flag[dir[0]][dir[1]] = 1;
                    stack.push(dir);
                }
            }
        }
//        Arrays.stream(image).forEach(p -> System.out.println(Arrays.toString(p)));
        return image;
    }
}